//搜索二维矩阵

package Leetcode;

class solution_074 {
    public static boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        // 对第一行使用二分查找
        int left = 0;
        int right = m - 1;
        int mid = 0;
        while (left <= right) {
            mid = (left + right) / 2;
            if (matrix[mid][0] == target)
                return true;
            else if (matrix[mid][0] < target)
                left = mid + 1;
            else
                right = mid - 1;
        }
        // System.out.println(mid);
        // 对对应行使用二分查找
        int line = matrix[mid][0] > target ? mid - 1 : mid;
        System.out.println(line + "@" + left);
        // 如果超过数组下界则直接返回
        if (line < 0)
            return false;
        left = 0;
        right = n - 1;
        while (left <= right) {
            mid = (left + right) / 2;
            if (matrix[line][mid] == target)
                return true;
            else if (matrix[line][mid] < target)
                left = mid + 1;
            else
                right = mid - 1;
        }
        return false;
    }

    public static void main(String[] args) {
        int[][] matrix = new int[][] { { 1, 3, 5, 7 }, { 10, 11, 16, 20 }, { 23, 30, 34, 60 } };
        int target = 3;
        searchMatrix(matrix, target);
    }
}

public class Solution074 {

}
